package DP;



/**
 * 32.最长有效括号
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 */
public class longestValidParentheses {
    public int longestValidParentheses(String s) {
        int n = s.length();
        if (n == 0) return 0;
        int[] dp = new int[n];  // dp[i] 表示以 i 结尾的最长有效括号长度
        int max = 0;
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else { // s.charAt(i - 1) == ')'
                    int j = i - dp[i - 1] - 1; // 找可能匹配的 '('
                    if (j >= 0 && s.charAt(j) == '(') {
                        dp[i] = dp[i - 1] + 2;
                        if (j - 1 >= 0) {
                            dp[i] += dp[j - 1];
                        }
                    }
                }
                max = Math.max(max, dp[i]);
            }
        }
        return max;
    }
}
